//https://www.nowcoder.com/practice/29311ff7404d44e0b07077f4201418f5?tpId=13&tqId=2285751&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13
// 这个题基本是想到了，但是不好码代码的；重要！！！

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    // 0123456789101112131415...
    int findNthDigit(int n) {
        if (n == 0 ) return 0;
        // write code here
        int digit = 1;
        long start = 1;
        long sum  = 9;
        while (n > sum) {
            n = n - sum;
            start = start * 10;
            digit = digit + 1;
            sum = 9 * start * digit;
        }
        //定位n在哪个数字上
        int num = start + (n - 1) / digit;
        //定位n在数字的哪一位上
        int index = (n - 1) % digit;
        return to_string(num)[index] - '0';
    }
};


#include <cmath>
#include <string>
#include <cmath>
#include <string>
class Solution2 {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    // 0123456789101112131415...
    long beginNumber(long digits) {
        if (digits == 1) return 0;
        return std::pow(10,digits-1);
    }
    long digitAtIndex(long index,long digits) {
        long number = beginNumber(digits) + index/digits;
        long bit = index%digits;
        long res = std::to_string(number)[bit] - '0';
        return res;
    }
    long countOfIntegers(long digits) {
        if (digits == 1) return 10;
        long count = (int) std::pow(10,digits-1);
        return 9*count;
    }
    long findNthDigit(int index) {
        if (index < 0) return -1;
        long digits = 1;
        while(true) {
            long numbers = countOfIntegers(digits);
            if(index < numbers*digits) {
                return digitAtIndex(index,digits);
                break;
            }
            index -= numbers*digits;
            digits++;
        }
        return -1;
    }
};